package sysu.el.graph.datagraph.algor;

import sysu.el.array.idx.ArrIdx;
import sysu.el.array.ints.ArrInt;
import sysu.el.audit.MaxInt;
import sysu.el.graph.datagraph.DataGraphMan;
import sysu.el.graph.datagraph.DataMan;
import sysu.el.graph.undi.UndiGT;
import sysu.el.graph.undi.algor.ConnectedBranchSearcher;
import sysu.el.graph.undi.algor.UndiBFSAlgor;
import sysu.el.matrix.ints.MatInt;

public class Trinity {
	public UndiGT rootGraph = null;
	public DataGraphMan manTree = null;
	public Trinity(UndiGT g){
		int n = g.getNodeNum();
		int id[] = new int[n];
		for (int i=0; i<n; i++)
			id[i] = i;
		rootGraph = g;
		manTree = DataGraphMan.wrap(ArrIdx.wrap(id), g);
		
		// Level One.
		Trinity.getConnectedSubGraphes(manTree);
		// Level Two.
		for (DataMan e : manTree.children){
			DataGraphMan e0 = (DataGraphMan) e;
			Trinity.getBranches(e0);
		}
		// Level Three.
	}
	
	static DataGraphMan[] getConnectedSubGraphes(DataGraphMan root){
		
		ConnectedBranchSearcher cbs = new ConnectedBranchSearcher(root.data);
		cbs.searching();
		int n = cbs.branches.size();
		
		DataGraphMan[] d = new DataGraphMan[n];
		for (int i=0; i<n; i++){
			int faId[] = cbs.branches.get(i);
			int roId[] = root.getIdxes(faId.length, faId);
			int w[][] = MatInt.getSubMatrix(root.data.weight.w, faId.length, faId);
			UndiGT sub = new UndiGT(w.length, w);
			
			d[i] = DataGraphMan.wrap(ArrIdx.wrap(roId), sub);
			root.addNode(d[i]);
		}
		
		return d;
	}
	
	
	static DataGraphMan[] getBranches(DataGraphMan root){
		
		UndiBFSAlgor bfs = new UndiBFSAlgor(root.data.getNodeNum());
		// Find out the node with maximum degree
		int max = Integer.MIN_VALUE;
		int maxId = -1;
		for (int i=0; i<root.data.getNodeNum(); i++){
			if (root.data.getDegree(i) > max){
				maxId = i;
				max = root.data.getDegree(i);
			}
		}
		System.out.println("MaxId: \t" + maxId);
		bfs.bfsWithout(maxId, root.data.adjNodes);
		int n = bfs.ans.size();
		DataGraphMan[] d = new DataGraphMan[n];
		for (int i=0; i<n; i++){
			int faId[] = bfs.ans.get(i);
			int roId[] = root.getIdxes(faId.length, faId);
			int w[][] = MatInt.getSubMatrix(root.data.weight.w, faId.length, faId);
			UndiGT sub = new UndiGT(w.length, w);
			d[i] = DataGraphMan.wrap(ArrIdx.wrap(roId), sub);
			root.addNode(d[i]);
		}
		
		return d;
	}
	
}
